package com.hspedu.newData.dmsxl.树.二叉树路径.递归加回溯组合;

import com.hspedu.newData.dmsxl.ds.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-04-23 
 * @Version: 1.0
 */

public class LC257二叉树的所有路径 {
    List<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return res;

        ArrayList<Integer> list = new ArrayList<>();
        getPath(root,list);
        return res;
    }

    public void getPath(TreeNode root,List list){
        list.add(root.val);
        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < list.size() - 1; i++) {
                sb.append(list.get(i)).append("->");
            }
            sb.append(list.get(list.size() - 1));
            res.add(sb.toString());
            return;
        }

        if (root.left != null) {
            getPath(root.left,list);
            list.remove(list.size() - 1); // 回溯
        }
        if (root.right != null){
            getPath(root.right,list);
            list.remove(list.size() - 1); // 回溯
        }

    }
}
